package cn.edu.zufe.mjt.graph;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 图的存储
 * 题目描述:
 * 给定两张有向图 A 和 B，其中图 A 以邻接矩阵形式给出，图 B 以邻接表形式给出。请判断这两张图是否完全一样。
 * 我们将“完全一样”的定义为:每个节点的邻居集合完全一致。
 * 输入
 * 输入的第一行包含两个整数 n，表示图的节点数。
 * 接下来的n行，给出图 A 的邻接矩阵。该矩阵的第讠行第j列表示节点i和节点j之间是否有边。如果存在边，则该位置的值为 1，否则为 0。
 * 接下来的n行，给出图 B 的邻接表。每行第一个数node,后面跟的第一个数k表示接下来输入k个数val表示节点node向这些节点val连一条边
 * 输出
 * 如果图 A 和图 B 完全一样，则输出"YES";否则输出“NO"。
 * 注意
 * 图 A 和图 B 是有向图，即如果 A[i][j]= 1，那么i到j有条有向边。
 * ·节点编号从1到 n。
 * ·图 A 和图 B 的节点数相同。
 * 数据范围:
 *   1 ≤ n ≤ 10^3
 * 。图 A 的邻接矩阵大小为 n x n，其中每个元素为 0或 1。
 * 。图 B 的邻接表中每个节点的邻居数量不超过 n - 1。
 */
public class GraphStorage {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] graphA = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                graphA[i][j] = scanner.nextInt();
            }
        }

        int[] edge = {1, 2, 1, 3, 1, 4, 2, 3, 2, 5, 3, 4};
        List<Set<Integer>> randomAdjList = generateRandomAdjList(n);
        System.out.println("随机生成的邻接表:");
        for (int i = 0; i < randomAdjList.size(); i++) {
            System.out.println("节点 " + (i + 1) + ": " + randomAdjList.get(i));
        }
    }

    public static void adjacencyMatrix(int[][] graph) {
        int n = graph.length;
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(graph, visited, i);
            }
        }
    }

    public static void adjacencyList(int[][] graph) {
        int n = graph.length;
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(graph, visited, i);
            }
        }
    }

    public static void dfs(int[][] graph, boolean[] visited, int node) {
        visited[node] = true;
        System.out.print(node + " ");
        for (int i = 0; i < graph.length; i++) {
            if (graph[node][i] == 1 &&!visited[i]) {
                dfs(graph, visited, i);
            }
        }
    }

    // 随机生成邻接表
    public static List<Set<Integer>> generateRandomAdjList(int n) {
        // 对于 每个节点，维护一个邻居列表，且至少一条边
        List<Set<Integer>> adjList = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            adjList.add(new HashSet<>());
        }
        // 随机生成边
        for (int i = 0; i < n; i++) {
            int j = (int) (Math.random() * n);
            if (i == j) {
                continue;
            }
            adjList.get(i).add(j + 1);
            adjList.get(j).add(i + 1);
        }
        return adjList.stream().filter(s -> s.size() != 0).collect(Collectors.toList());
    }



    // 生成邻接表
    public static List<List<Integer>> generateAdjList(int[] v) {
        if (v == null || v.length == 0) {
            return new ArrayList<>();
        }
        int nodeNum = Arrays.stream(v).max().getAsInt();
        int n = v.length;
        List<List<Integer>> adjList = new ArrayList<>(n/2);

        // 初始化邻接表
        for (int i = 0; i < nodeNum; i++) {
            adjList.add(new ArrayList<>());
        }
        for (int i = 0; i < n / 2; i++) { // 根据数组生成邻接表
            int u = v[2 * i];
            int v1 = v[2 * i + 1];
            adjList.get(u - 1).add(v1);
            adjList.get(v1 - 1).add(u);
        }
        return adjList;
    }

    // 根据邻接矩阵生成邻接表
    public static  List<List<Integer>> generateAdjList(int[][] v) {
        if (v == null || v.length == 0) {
            return new ArrayList<>();
        }
        int nodeNum = v.length;
        int n = v[0].length;
        List<List<Integer>> adjList = new ArrayList<>(nodeNum);

        // 初始化邻接表
        for (int i = 0; i < nodeNum; i++) {
            adjList.add(new ArrayList<>());
        }
        for (int i = 0; i < nodeNum; i++) {
            for (int j = 0; j <= i; j++) {
                if (v[i][j] == 1) {
                    adjList.get(i).add(j);
                    adjList.get(j).add(i);
                }
            }
        }
        return adjList;
    }
}
